COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00015 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a38.tex[106,phy] \today\hfill}

\bigskip
\line{[Rewrite and expand. Array and subarray assignment is omitted]\hfil}

\bigskip
\line{{\bf Arrays.} [RWF: Assumes subrange types] [Define subscripts or indices]
\hfil}

An {\sl array\/} is a set of storage variables that stores the values
of a function of one or more ordinal variables. These variables, like
other storage variables, have no defined initial value, and may be
used and changed by the program. If {\tt A} is the array name,
and $f$ is the function of which {\tt A} stores the values, then
{\tt A[I,J]} is the name of the storage variable where $f(I,J)$
is kept.

We might, for example, compute the first 25 Fibonacci numbers
$f↓0,f↓1,\ldots,f↓{24}$ and store them in the array {\tt FIB} by this
program fragment:

{\obeylines\obeyspaces\let =\ \tt
        A:=0; B:=1;
        FOR I:=0 TO 24 DO
            BEGIN
            FIB[I]:=A;
            C:=A+B; A:=B; B:=C
            END;
}

\noindent
after which they could be printed in reverse order by

{\obeylines\obeyspaces\let =\ \tt
        FOR J:=24 DOWNTO 0 DO
            WRITELN(J,FIB[J])
}

Just as storage variables, unlike the ``variables'' of mathematics,
may change over time, so may the functions stored in arrays. Here is
a program fragment that
reads a line of text, counts how many times each
letter appears, and prints out the counts at the end. While reading,
the {\tt COUNT} array contains, for each letter, the number of times
that letter has occurred.

{\obeylines\obeyspaces\let =\ \tt
        FOR C:='A' TO 'Z' DO (* C OF TYPE CHAR *)
            COUNT[C]:=0; (* INITIALIZE *)
        WHILE NOT EOLN DO
            BEGIN
            READ (C);
            COUNT[C]:=COUNT[C]+1
            END;
        FOR C:='A' TO 'Z' DO
            WRITELN(C,COUNT[C])
}

The allowed operations on arrays include not only finding the value
of the function on any argument within range (a~{\sl value access\/} to the
array) but also assigning a new value to the function on any argument
within range (a~{\sl reference access\/} to the array). This permits
computing and using the values in any convenient order.

For example, a program to read 150 numerical data from a file and print
them numbered in three columns, can begin by reading each datum and letting
it be the value of the array for one argument.  After all have been read
and stored, the program finds the values stored in the array, in the
correct order for printing.  The program, in outline, is this:

\vfill\eject

{\obeylines\obeyspaces\let =\ \tt
        (Declarations)
        BEGIN
        FOR I:=1 TO 150 DO
            READ(A[I]);
        FOR J:=1 TO 50 DO
            WRITELN(J,A[J],J+50,A[J+50],J+100,A[J+100])
        END.
}

If $A$ is an array with index type [define]
$T↓1$ and component type [define]
$T↓2$, and $I$ is any
expression of type~$T↓1$, we can use A[I] to mean the value of {\tt A} for the
argument~{\tt I}.  This program fragment:

{\obeylines\obeyspaces\let =\ \tt
        S:=0;
        FOR J:=0 TO 2 DO
            S:=S+A[J+1];
        WRITE(S)
}

\noindent
prints the value of {\tt A[1]+A[2]+A[3]}.  If {\tt A[I]} appears in an assignment
context, a new value is given to {\tt A} for the argument~{\tt I}; 
after executing this program fragment:

{\obeylines\obeyspaces\let =\ \tt
        FOR I:=1 TO 3 DO
            IF I=2 THEN A[I]:=3.0
            ELSE READ(A[I])
}

\noindent
with the input file  {\tt 5.7\ 6.9}
we will have {\tt A[1]=5.7}, {\tt A[2]=3.0}, {\tt A[3]=6.9}.

In Pascal, an array type is of the form

{\obeylines\obeyspaces\let =\ \tt
        ARRAY[$T↓1$] OF $T↓2$
}

\noindent
where $T↓1$ is the index type, and $T↓2$ the component type.  The index type
must be ordinal, of small enough range for the array to be kept in the
computer's main memory.
The component type can be any type for which assignment
is possible, i.e., any non-file type.  [RWF: Check if component type can be
a file type.]
An array is declared in the same way a
program variable is, using an array type.  The declaration

{\obeylines\obeyspaces\let =\ \tt
        VAR A: ARRAY[1..10] OF REAL;
}

\noindent
or, better,

{\obeylines\obeyspaces\let =\ \tt
        ...
        ...
        TYPE ARRAYDEMO=ARRAY[1..10] OF REAL;
        ...
        ...
        VAR A: ARRAYDEMO;
}

\noindent
declares {\tt A} as an array with integer indices in (1,10), with real number
components.

An array could be declared

{\obeylines\obeyspaces\let =\ \tt
        VAR CODE: ARRAY['A'..`Z'] OF CHAR;
}

\noindent
Such an array could be used to store a function from letters to letters for
decoding a substitution cipher.

Arrays may have more than one index.  An array to hold a tax table for
specified income (in \$1000s) and family size would be declared:

{\obeylines\obeyspaces\let =\ \tt
        VAR TAXTBL: ARRAY[1..2000, 0..20] OF INTEGER
}

\noindent
or, giving the array type a name of its own,

{\obeylines\obeyspaces\let =\ \tt
        ...
        ...
        TYPE TXTBTY=ARRAY[1..2000, 0..20] OF INTEGER;
        ...
        ...
        VAR TXTBL:TXTBTY
        ...
        ...
}

An array with one index ({\sl one-dimensional array\/}) is often
envisioned as a row or column of variables labeled with the values of
its ordinal index type. If the array~{\tt A} were declared

{\obeylines\obeyspaces\let =\ \tt
        VAR A: ARRAY[1..3] OF CHAR;
}

\noindent
one would imagine it as

$$\vcenter{\tabskip0pt\offinterlineskip
\halign{\lft{\tt #}\quad&\vrule#&\strut\quad\hfill{#}\hfill\quad&\vrule#%
&\quad\hfill{#}\hfill\quad&\vrule#
&\quad\hfill{#}\hfill\quad&\vrule#\cr
&\omit&1&\omit&2&\omit&3&\omit\cr
&\multispan7\hrulefill\cr
&height2pt&\omit&&\omit&&\omit&\cr
A&&{\tt 'Q'}&&{\tt 'J'}&&{\tt 'Z'}&\cr
&\multispan7\hrulefill\cr}}
\qquad\hbox{or}\qquad
\vcenter{\tabskip0pt\offinterlineskip
\halign{\lft{#}\quad&\vrule#&\strut\quad\hfill{\tt #}\hfill\quad&\vrule#\cr
&\omit&A&\omit\cr
&\multispan3\hrulefill\cr
&height2pt&\omit&\cr
1&&'Q'&\cr
&\multispan3\hrulefill\cr
&height2pt&\omit&\cr
2&&'J'&\cr
&\multispan3\hrulefill\cr
&height2pt&\omit&\cr
3&&'Z'&\cr
&\multispan3\hrulefill\cr}}$$

A two-dimensional array is conventionally imagined as a rectangular table, with
rows corresponding to the values of its first ordinal index, and columns
corresponding to the second. If {\tt B} is declared

{\obeylines\obeyspaces\let =\ \tt
        VAR B: ARRAY[2..4,-1..2] OF INTEGER
}

\noindent
one could imagine it as

$$\vbox{\tabskip0pt\offinterlineskip
\halign{\lft{#}\quad&\vrule#&\strut\quad\hfill{#}\hfill\quad&\vrule#%
&\quad\hfill{#}\hfill\quad&\vrule#
&\quad\hfill{#}\hfill\quad&\vrule#
&\quad\hfill{#}\hfill\quad&\vrule#\cr
{\tt B}&\omit&$-1$&\omit&0&\omit&1&\omit&2&\omit\cr
&\multispan9\hrulefill\cr
&height2pt&\omit&&\omit&&\omit&&\omit&\cr
2&&{\tt B[2,-1]}&&{\tt B[2,0]}&&\phantom{\tt B[2,0]}&&&\cr
&\multispan9\hrulefill\cr
&height2pt&\omit&&\omit&&\omit&&\omit&\cr
3&&&&&&&&&\cr
&\multispan9\hrulefill\cr
&height2pt&\omit&&\omit&&\omit&&\omit&\cr
4&&&&&&&&{\tt B[4,2]}&\cr
&\multispan9\hrulefill\cr}}$$


{\rmn
{\narrower\smallskip\noindent
{\bf An exercise in the use of arrays.}

\noindent
Write a program which reads the degree ($≤20$) of a 
polynomial, then the coefficients
starting with the constant term.  The program should print the polynomial, its
square, and its cube.  Try it on the polynomial
$$16 - 32x + 24x↑2 - 8x↑3 + x↑4\,.$$
\smallskip}
}

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March 28, 1984

\bye